from abc import abstractclassmethod
from typing import List
from typing import Optional

class Solution:

# 539. 最小时间差
# https://leetcode-cn.com/problems/minimum-time-difference/
    def findMinDifference(self, timePoints: List[str]) -> int:
        # 输入要求s1 < s2
        def diff(s1: str, s2: str) -> int:
            res1 = s1.split(':')
            res2 = s2.split(':') 
            r1 = 60 *(int(res2[0]) - int(res1[0])) + (int(res2[1]) - int(res1[1]))
            return min(r1, 1440 - r1)     
        timePoints.sort()
        i, size = 0, len(timePoints)
        mindiff = 24 * 60
        while (i < size):
            cur = timePoints[i]
            r = 0
            if i == size - 1:
                r = diff(timePoints[0], cur)
            else : 
                next = timePoints[i + 1]   
                r = diff(cur,next)
            if (r < mindiff):
                mindiff = r
            i += 1
        return mindiff

# 3.无重复字符的最长子串
# https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
# start 窗口起始地址, 碰到重复字符时更新索引
# cache 存放字符在字符串的索引
# len 存放当前最长字串长度, 碰到重复字符且重复所在位置在窗口之内, 更新窗口起始地址
# 最重要的就是正确维护窗口起始地址, 窗口更新的准确条件是窗口不能包含重复字符 
# 1. 记录窗口的起始地址， 2. 记录字符的索引 
    def lengthOfLongestSubstring(self, s: str) -> int:
        len, start, cache = 0, 0, {}
        for index, char in enumerate(s):
            if (char in cache and cache[char] >= start) :
                start = cache[char] + 1
                cache[char] = index
            else :
                cache[char] = index
                # cur = index - start + 1
                # len = math.max(len, cur)
                if (index - start >= len):
                    len +=1
            
        return len

    def LongestSubstring(self, s: str) -> str:  
        len, start, cache = 0, 0, {}
        res = ''
        for index, char in enumerate(s):
            if (char in cache and cache[char] >= start) :
                start = cache[char] + 1
                cache[char] = index
            else :
                cache[char] = index
                # cur = index - start + 1
                # len = math.max(len, cur)
                if (index - start >= len):
                    len +=1
                    res = s[start: start+ len]
            
        return res 


    # 4.寻找两个有序数组的中位数
    # https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
    # 关键是转换为求第k小数
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def findK(k:int) ->int:
            l1, l2, r1, r2 = 0, 0, len(nums1), len(nums2)
            res = 0
            while 1 :
                if (l1 >= r1) :
                    res = nums2[l2 + k - 1]
                    break
                if (l2 >= r2) :
                    res = nums1[l1 + k -1]
                    break
                if (k == 1) :
                    res = min(nums1[l1], nums2[l2])
                    break
                v1 = nums1[l1 + k//2 - 1] if (l1 + k//2 - 1 < r1) else infinty
                v2 = nums2[l2 + k//2 -1] if (l2 + k//2 - 1 < r2) else infinty
                if (v1 < v2) :
                    l1 += k//2
                else:
                    l2 += k//2
                k = k - k//2        
            return res
        
        l = len(nums1) + len(nums2) 
        res = 0.0
        if (l % 2 == 1):
            res = 1.0 * findK((l + 1) // 2)
        else :
            v1 = findK((l + 1) // 2) 
            v2 = findK( (l + 2) // 2)    
            res = (v1 + v2) / 2.0  
        return res

    # 5.最长回文子串
    # https://leetcode-cn.com/problems/longest-palindromic-substring/

    # method 1. violent solution
    ## go through all the substrings to find the longest
    # def longestPalindrome(self, s: str) -> str:
    #     def isPalindrome(sub: str) -> bool:
    #         if (sub == sub[::-1]):
    #             return True
    #         else:
    #             return False
    #     res = ''
    #     size = 0
    #     l =  len(s)
    #     if (l == 1) :
    #         return s
    #     for i in range(l) :
    #         for j in range (l):
    #             if (j < i) :
    #                 continue
    #             if ( (j+1 -i > size) and isPalindrome(s[i:j+1])) :
    #                 size = j+1 - i
    #                 res = s[i:j+1]
    #     return res

    # method 1.1. since it is the longest string , go through from the longest to shortest
    # def longestPalindrome(self, s: str) -> str:
    #     def isPalindrome(sub: str) -> bool:
    #         if (sub == sub[::-1]):
    #             return True
    #         else:
    #             return False
    #     res = ''
    #     size = 0
    #     l =  len(s)
    #     if (l == 1) :
    #         return s
    #     for i in range(l) :
    #         for j in range (l,0,-1):
    #             if (j < i) :
    #                 continue
    #             if ( (j -i > size) and isPalindrome(s[i:j])) :
    #                 size = j - i
    #                 res = s[i:j]
    #     return res

    # method 2, take each charcter as the center to find the longest palindrome string
    # def longestPalindrome(self, s: str) -> str:
    #     def findPalindrome(l: int, r: int):
    #         while(l >=0 and r < len(s) and s[l] == s[r]):
    #             l = l - 1
    #             r = r + 1
    #         return s[l + 1: r]
    #     res = ''    
    #     for i in range(len(s)):
    #         s1 = findPalindrome(i, i)
    #         s2 = findPalindrome(i, i + 1) 
    #         if (len(s1) > len (res)):
    #             res = s1
    #         if (len(s2) > len (res)):
    #             res = s2 
    #     return res
    # method 2.2, take each charcter as the center to find the longest palindrome string
    # use extra concatenation character to converts the string length to an odd number  
    def longestPalindrome(self, s: str) -> str: 
        def findPalindrome(cen: int) -> str:
            l, r = cen, cen;
            while(l >=0 and r < len(s) and s[l] == s[r]):
                l = l - 1
                r = r + 1
            return s[l + 1: r] 
        s = '#' + '#'.join(list(s)) + '#'
        res = ''
        for i in range(len(s)):
            s1 = findPalindrome(i)
            if (len(s1) > len(res)):
                res = s1

        return res[1::2]        
    # 10.正则表达式匹配
    # https://leetcode-cn.com/problems/regular-expression-matching/
    # method dynamic programming
    # my thought
    def isMatch(self, s: str, p: str) -> bool:
        def match(i, j) -> bool:
            if (i == 0) :
                return False
            return p[j - 1] == '.' or s[i - 1] ==  p[j - 1]
        m, n = len(s), len(p)
        # f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配
        f = [[False] * (n + 1) for _ in range(m + 1)]
        # 都为空字符为真
        f[0][0] = True
        for i in range(0, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    # 把字符和*看做整体, *号前两位是否匹配决定当前能否匹配
                    # 不担心越界,是因为题目保证*不会出现在开头
                   f[i][j] |= f[i][j - 2] 
                    # 比较同*前面字符是否匹配, 一旦匹配,相当于忽略s中的该字符
                   if match(i, j - 1) :
                      f[i][j] |= f[i - 1][j]
                      
                else:
                    if match(i, j):
                      f[i][j] = f[i - 1][j - 1]

        return f[m][n]
    

    # 11.盛最多水的容器
    #
    # https://leetcode-cn.com/problems/container-with-most-water/
    # 初次见题，只有暴力方案
    # 题解之后：
    # 可以通过双指针降低复杂度,能用双指针的关键找到不走回头路的方法,本题谁小谁移动
    # method1  violent solution
    # my thought
    # def maxArea(self, height: List[int]) -> int:
    #     def area(i:int, j:int) -> int:
    #         return (j-i) * min(height[i], height[j])

    #     max = 0
    #     size = len(height)
    #     for index, h in  enumerate(height):
    #         for j in range(index+1, size):
    #             v = area(index, j)
    #             if (v > max):
    #                 max = v
            
    #     return max

    # method2  dobule pointer
    # my thought, keep move the pointer on the left and right sides until they meet
    def maxArea(self, height: List[int]) -> int:
        def area(i:int, j:int) -> int:
            return (j-i) * min(height[i], height[j])
        max = 0
        size = len(height)
        i = 0;
        j = size -1;
        while (i < j):
            v = area(i, j)
            if (v > max) :
                max = v
            if  height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max    

    # 15.三数之和
    # https://leetcode-cn.com/problems/3sum/
    # method 
    # 难点: 如何去重
    # 如何避免重复
   

    # 题解之后：
    # 1. 去重是个很麻烦的问题,可以先排序避免这个问题
    # 2. 当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，
    # 将枚举的时间复杂度从 O(N^2)减少至O(N)


    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def _sum(i:int, j:int, k:int) -> int:
            sum = nums[i] + nums[j] + nums[k]
            return sum  
        size = len(nums)   
        if (size < 3) :
            return []
        nums.sort()   
        i, j, k = 0, 0, size - 1
        res=[]

        def noSame(arr:List[int], j, k):
            if (arr[1] == nums[j] and arr[2] == nums[k]) :
                return False
            return True    

        while (nums[i] <= 0 and k - i >=2) :
            # 新一轮循环双指针要复位
            ## 判断第一个数是不是重复
            if i > 0 and nums[i] == nums[i-1]:
                i += 1
                continue
            j = i + 1
            k = size - 1
            while(j < k):
                if _sum(i, j, k) > 0 :
                    k -= 1
                elif _sum(i, j, k) < 0:
                    j += 1
                else:
                    l = len(res)
                    if (l == 0):
                        res.append([nums[i], nums[j], nums[k]])
                    else:
                        ## 判断后两个数是不是重复
                        if(noSame(res[l - 1], j, k)) :
                            res.append([nums[i], nums[j], nums[k]])       
                    j+=1
                    k-=1    
            i += 1
        return res
                      
    # 17.电话号码的字母组合
    # https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
    # method 
    # my thought


    # void backtracking(参数) {
    # if (终止条件) {
    #     存放结果;
    #     return;
    # }

    # for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    #     处理节点;
    #     backtracking(路径，选择列表); // 递归
    #     回溯，撤销处理结果
    # }
    # }
    def letterCombinations(self, digits: str) -> List[str]:
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        res=[]
        if (len(digits) == 0) : 
            return []

        def backtracking():

        

        return res


    # 19.删除链表的倒数第N个节点
    # https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
    # method 
    # my thought
    # def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    #     return None


    # 20有效的括号
    # https://leetcode-cn.com/problems/valid-parentheses/
    # method 
    # my thought
    def isValid(self, s: str) -> bool:
        return True

    #230. 二叉搜索树中第K小的元素 
    # 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
    # https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/   
    # method1 
    # my thought: The search tree is converted to an ordered array by middle order traversal
    # def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    #     result = []
    #     def traverse(root: Optional[TreeNode]):
    #         if (root == None) :
    #             return
    #         traverse(root.left)
    #         result.append(root.val)
    #         traverse(root.right)
    #     traverse(root)
    #     return result[k - 1]

    # method2  
    # stack store smallest ones, in fact, method1 can achieve the same effect by adding judgments
    # def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    #     stack = []
    #     while (root or stack):
    #         while(root):
    #             stack.append(root.val)
    #             root = root.left
    #         root = stack.pop() 
    #         k -= 1
    #         if (k == 0) :
    #             return root.val
    #         root = root.right      

    # methos 3
    # def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    #         cache = {}
    #         def treeNodeCount(root: Optional[TreeNode]) -> int:
    #             if (not root) :
    #                 return 0
    #             if (root in cache):
    #                 return cache[root] 
    #             else:
    #                 count = 1 + treeNodeCount(root.left) + treeNodeCount(root.right);
    #                 cache[root] = count
    #                 return count       
    #         leftN = treeNodeCount(root.left)
    #         if (k == leftN + 1) :
    #             return root.val
    #         elif(k <= leftN):
    #             return self.kthSmallest(root.left, k)
    #         else:
    #             return self.kthSmallest(root.right, k - (leftN + 1)) 
## test
solution = Solution()
# print(solution.lengthOfLongestSubstring("tmmzuxt"))
# print(solution.LongestSubstring("tmmzuxt"))

# print(solution.findMedianSortedArrays([1,2,4],[3,5]))

# print(solution.longestPalindrome("mozblnzrszxtdjmwvgeovtxoftpcsbnjryogrnibiiqfexljlfikfcxvrzrpfvugtdjrlkgvkmrqgeltifdehsewpdhpjpnuobmuozopmglnocqcozvratjpzrklexqdeuvvzfjkuknkkoynxptrgtzadmpfdkphfjhdulhzncoofmmrwqjxeyhodfavcgpjmohohuztezdxegqzbaaobzrqptuqsvwnfdneyccbkgkjafztytwuppvleukdqqzyeiltsvoqbxupbasiityganofxijucwzqgtdyxljociwwjdrnfnfbwyymmvbuvbrdnvcubzkohknbsneutrcukfiqqhfviqdsbtrldipenqifdcrenpuyaqvkparycksurhbtjppwhezbcgocamurdawimkzzkmiwadrumacogcbzehwppjtbhruskcyrapkvqayupnercdfiqnepidlrtbsdqivfhqqifkucrtuensbnkhokzbucvndrbvubvmmyywbfnfnrdjwwicojlxydtgqzwcujixfonagytiisabpuxbqovstlieyzqqdkuelvppuwtytzfajkgkbccyendfnwvsqutpqrzboaabzqgexdzetzuhohomjpgcvafdohyexjqwrmmfoocnzhludhjfhpkdfpmdaztgrtpxnyokknkukjfzvvuedqxelkrzpjtarvzocqconlgmpozoumbounpjphdpweshedfitlegqrmkvgklrjdtguvfprzrvxcfkifljlxefqiibinrgoyrjnbscptfoxtvoegvwmjdtxzsrznlbzom"))
# print(solution.kthSmallest([1,2,4],[3,5]))
# print(solution.findMinDifference(["23:59","00:00"]))
# print(solution.threeSum([-1,0,1,2,-1,-4]))
print(solution.letterCombinations("23"))